{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #删除链表的倒数第 N 个结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeNthFromEnd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表的倒数第 N 个结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表，删除链表的倒数第&nbsp;<code>n</code><em>&nbsp;</em>个结点，并且返回链表的头结点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg\" style=\"width: 542px; height: 222px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5], n = 2\n",
    "<strong>输出：</strong>[1,2,3,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], n = 1\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], n = 1\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中结点的数目为 <code>sz</code></li>\n",
    "\t<li><code>1 &lt;= sz &lt;= 30</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= sz</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>能尝试使用一趟扫描实现吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 19&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/\">https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [SLwz0R](https://leetcode.cn/problems/SLwz0R/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [SLwz0R](https://leetcode.cn/problems/SLwz0R/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[1]\\n1', '[1,2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/#%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%AC-k-%E4%B8%AA%E8%8A%82%E7%82%B9\n",
    "# 分析：删除某个节点，相当于获得一条新链表\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # 返回链表的倒数第 k 个节点\n",
    "    def findFromEnd(self, head, k):\n",
    "        p1 = head\n",
    "        # p1 先走 k 步\n",
    "        for i in range(k):\n",
    "            p1 = p1.next\n",
    "        \n",
    "        p2 = head\n",
    "        # p1 和 p2 同时走 n - k 步\n",
    "        while p1:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        \n",
    "         # p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点\n",
    "        return p2\n",
    "\n",
    "\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        # 虚拟头结点\n",
    "        dummy = ListNode(0)\n",
    "        # 这里必须要先连上head，因为下面2句代码相当于在原地进行修改\n",
    "        # 虚拟头结点，可以避免边界问题。如head=[1]，要删除倒数第一个节点，那么head.next.next就会报错中断程序\n",
    "        dummy.next = head\n",
    "\n",
    "        # 删除倒数第 n 个，要先找倒数第 n + 1 个节点,这样才能获取到第n个要删除的节点，才能获取到n的下一个节点\n",
    "        # 如果先获取到第n个节点，那么n前面那个就不知道了，就没法把n前面那个和n.next链接起来了\n",
    "        x = self.findFromEnd(dummy, n+1)\n",
    "\n",
    "        x.next = x.next.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def getLength(head:ListNode)->int:\n",
    "            length=0\n",
    "            while head:\n",
    "                length+=1\n",
    "                head = head.next\n",
    "            return length\n",
    "        dummy=ListNode(0,head)\n",
    "        length=getLength(head)\n",
    "        cur =dummy\n",
    "        for i in range(1,length-n+1):\n",
    "            cur=cur.next\n",
    "        cur.next =cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        p = dummy\n",
    "        q = dummy\n",
    "        count= 0\n",
    "        while p.next != None:\n",
    "            count = count + 1\n",
    "            p = p.next\n",
    "        for i in range(0,count - n):\n",
    "            q = q.next\n",
    "        q.next = q.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(next = head)\n",
    "        cur, node = dummy, dummy\n",
    "        for _ in range(n):\n",
    "            node = node.next\n",
    "        while node.next:\n",
    "            cur, node = cur.next, node.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        slow, fast = dummy, dummy\n",
    "        # fast往前走n步\n",
    "        while n > 0:\n",
    "            fast = fast.next\n",
    "            n -= 1\n",
    "        # fast和slow同时往前走，走到fast.next为空，此时slow.next就是要删除的节点\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        # slow指向下下个节点，指定节点被删除\n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def getlenght(root):\n",
    "            L = 0\n",
    "            while root:\n",
    "                root = root.next\n",
    "                L += 1\n",
    "            return L\n",
    "        \n",
    "        temp = ListNode(0, head)\n",
    "        L = getlenght(head)\n",
    "        cur = temp\n",
    "        for i in range(1, L-n+1):\n",
    "            cur = cur.next # 0->head, L-(n+1)=L-n-1->倒数第n+1个\n",
    "        cur.next = cur.next.next\n",
    "        return temp.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        left = right = head\n",
    "        count = 0\n",
    "        while count < n:\n",
    "            right = right.next\n",
    "            count += 1\n",
    "        if not right:\n",
    "            return head.next\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        left.next = left.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head == None:\n",
    "            return None\n",
    "        rsta = ListNode(-1)\n",
    "        rsta.next = head\n",
    "\n",
    "        cur = head\n",
    "        pre = rsta\n",
    "        fast = head\n",
    "\n",
    "        for i in range(0,n):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            pre = cur\n",
    "\n",
    "            cur = cur.next\n",
    "        pre.next = cur.next\n",
    "        return rsta.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        length = 0\n",
    "        tmp = head\n",
    "        while tmp:\n",
    "            length += 1\n",
    "            tmp = tmp.next\n",
    "        newHead = ListNode(0)\n",
    "        newHead.next = head\n",
    "        slow = newHead\n",
    "        fast = newHead\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return newHead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        cur1=cur2=head\n",
    "        while cur2:\n",
    "            if n<0:\n",
    "                cur1=cur1.next\n",
    "            n-=1\n",
    "            cur2=cur2.next\n",
    "        if n==0:\n",
    "            head=head.next \n",
    "        else:\n",
    "            cur1.next=cur1.next.next\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        current, length = head, 0\n",
    "        \n",
    "        while current:\n",
    "            current = current.next\n",
    "            length += 1\n",
    "\n",
    "        current = dummy\n",
    "        for _ in range(length - n):\n",
    "            current = current.next\n",
    "        \n",
    "        current.next = current.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0,head)\n",
    "        q=head\n",
    "        p=dummy\n",
    "        while q:\n",
    "            q=q.next\n",
    "            if n:\n",
    "                n-=1\n",
    "            else:\n",
    "                p=p.next\n",
    "        p.next = p.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "      hair = ListNode(0)\n",
    "      hair.next = head\n",
    "\n",
    "      count = 0\n",
    "      fast = slow = hair\n",
    "      while fast:\n",
    "        if count >= n:\n",
    "          pre = slow\n",
    "          slow = slow.next\n",
    "        fast = fast.next\n",
    "        count += 1\n",
    "      pre.next = slow.next\n",
    "      return hair.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        first=ListNode(0,head)\n",
    "        fast=slow=first\n",
    "        for i in range(n):\n",
    "            fast=fast.next\n",
    "        while fast.next:\n",
    "            fast=fast.next\n",
    "            slow=slow.next\n",
    "        slow.next=slow.next.next\n",
    "        return first.next\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def getlenght(root):\n",
    "            L = 0\n",
    "            while root:\n",
    "                root = root.next\n",
    "                L += 1\n",
    "            return L\n",
    "        \n",
    "        temp = ListNode(0, head)\n",
    "        L = getlenght(head)\n",
    "        cur = temp\n",
    "        for i in range(0, L-n):\n",
    "            cur = cur.next # 0->head, L-(n+1)=L-n-1->倒数第n+1个\n",
    "        cur.next = cur.next.next\n",
    "        return temp.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        temp = head\n",
    "        length = 0\n",
    "        while temp is not None:\n",
    "            temp = temp.next\n",
    "            length += 1\n",
    "\n",
    "        count = 0\n",
    "        temp = head\n",
    "        if length == n:\n",
    "            head = head.next\n",
    "            return head\n",
    "        while temp is not None:\n",
    "            # print(head)\n",
    "            count += 1\n",
    "            if count == length - n:\n",
    "\n",
    "\n",
    "                if count == length - 1:\n",
    "                    temp.next = None\n",
    "                \n",
    "                else:\n",
    "                    temp_next = temp.next\n",
    "                    temp.next = temp_next.next\n",
    "                return head\n",
    "            \n",
    "            temp = temp.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def getlenght(root):\n",
    "            L = 0\n",
    "            while root:\n",
    "                root = root.next\n",
    "                L += 1\n",
    "            return L\n",
    "        \n",
    "        temp = ListNode(0, head)\n",
    "        L = getlenght(head)\n",
    "        cur = temp\n",
    "        for i in range(0, L-n):\n",
    "            cur = cur.next # 0->head, L-(n+1)=L-n-1->倒数第n+1个\n",
    "        cur.next = cur.next.next\n",
    "        return temp.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(val=-1,next=head)\n",
    "        p1,p2 = dummy,dummy\n",
    "        for _ in range(n):\n",
    "            p2 = p2.next\n",
    "        while p2.next:\n",
    "            p1,p2 = p1.next,p2.next\n",
    "        p1.next = p1.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        fakeHead = ListNode(0)\n",
    "        fakeHead.next = head\n",
    "        fast = fakeHead\n",
    "        for i in range(n):\n",
    "            fast = fast.next\n",
    "        slow = fakeHead\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return fakeHead.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy_head = ListNode(-1)\n",
    "        dummy_head.next = head\n",
    "        cur = dummy_head\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        for _ in range(length - n):\n",
    "            cur = cur.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        cur = head\n",
    "        length = 0\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1\n",
    "            dummy = ListNode(0, head)\n",
    "        cur = dummy\n",
    "        for i in range(1, length - n + 1):\n",
    "            cur = cur.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "\n",
    "        dummyhead = ListNode(0, head)\n",
    "\n",
    "        slow, fast = dummyhead, dummyhead\n",
    "\n",
    "        while n:\n",
    "            n -= 1\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummyhead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        count = 0\n",
    "        cnt = head\n",
    "        while cnt:\n",
    "            count += 1\n",
    "            cnt = cnt.next\n",
    "\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "\n",
    "        if count == 1 and n == 1:\n",
    "            return None\n",
    "        if n == count:\n",
    "            return head.next\n",
    "        \n",
    "        index = 0\n",
    "        while index < count - n - 1:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            index += 1\n",
    "        \n",
    "        slow.next = fast.next\n",
    "\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        p = dummy\n",
    "        q = dummy\n",
    "        count= 0\n",
    "        while p.next != None:\n",
    "            count = count + 1\n",
    "            p = p.next\n",
    "        #if count == 1 and n == 1:\n",
    "            #return None\n",
    "        for i in range(0,count - n ):\n",
    "            q = q.next\n",
    "        q.next = q.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        rs = slow = fast = head\n",
    "\n",
    "        # 快指针先走n步\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "        if not fast:  # 走到头，删除的是第一个结点\n",
    "            return rs.next\n",
    "        \n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        h = ListNode(0, head)\n",
    "        p = q = h\n",
    "        for _ in range(n+1):\n",
    "            q = q.next\n",
    "        \n",
    "        while q:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        p.next = p.next.next\n",
    "\n",
    "        return h.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        t=ListNode(-1)\n",
    "        p=t\n",
    "        t.next=head\n",
    "        for i in range(n):\n",
    "            head=head.next\n",
    "        while head:\n",
    "            t=t.next\n",
    "            head=head.next\n",
    "        t.next=t.next.next\n",
    "        return p.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, val=0, next=None):\n",
    "# #         self.val = val\n",
    "# #         self.next = next\n",
    "# class Solution:\n",
    "#     # 快慢指针，right比left先走n步\n",
    "#     # right和left一起走，right到终点，left到n节点\n",
    "#     # 将left.next<-left.next.next\n",
    "#     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "#         left = right = head\n",
    "#         if not head:\n",
    "#             return []\n",
    "#         for _ in range(n):\n",
    "#             right = right.next\n",
    "#         if not right:\n",
    "#             return head.next\n",
    "#         # 直到right到终点\n",
    "#         while right.next:\n",
    "#             left = left.next\n",
    "#             right = right.next\n",
    "#         left.next = left.next.next\n",
    "#         return head\n",
    "#         # 返回头节点\n",
    "\n",
    "\n",
    "# 快慢指针\n",
    "# 快指针right比慢指针多走n步\n",
    "# 当快指针到达终点，慢指针到达第n个节点\n",
    "# left.next = left.next.next # 将第n个节点的后指针 替换未后后指针\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        left = right = head\n",
    "        count = 0 \n",
    "        while count < n:\n",
    "            right = right.next\n",
    "            count += 1\n",
    "# 没有第n个节点，直接返回head.next\n",
    "        if not right:\n",
    "            return head.next\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        left.next = left.next.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        p = None\n",
    "        p1 = head\n",
    "        p2 = head\n",
    "        for _ in range(n - 1):\n",
    "            p2 = p2.next\n",
    "        while p2.next:\n",
    "            p = p1\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        if p:\n",
    "            p.next = p1.next\n",
    "        else:\n",
    "            head = head.next\n",
    "        del p1\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "\n",
    "        fast = dummy\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "\n",
    "        slow = dummy\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, val=0, next=None):\n",
    "# #         self.val = val\n",
    "# #         self.next = next\n",
    "class Solution:\n",
    "    # 快慢指针，right比left先走n步\n",
    "    # right和left一起走，right到终点，left到n节点\n",
    "    # 将left.next<-left.next.next\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        left = right = head\n",
    "        if not head:\n",
    "            return []\n",
    "        for _ in range(n):\n",
    "            right = right.next\n",
    "        if not right:\n",
    "            return head.next\n",
    "        # 直到right到终点\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        left.next = left.next.next\n",
    "        return head\n",
    "        # 返回头节点\n",
    "\n",
    "\n",
    "# 快慢指针\n",
    "# 快指针right比慢指针多走n步\n",
    "# 当快指针到达终点，慢指针到达第n个节点\n",
    "# left.next = left.next.next # 将第n个节点的后指针 替换未后后指针\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "# #         self.next = next\n",
    "# class Solution:\n",
    "#     def removeNthFromEnd(self, head, n):\n",
    "#         left = right = head\n",
    "#         count = 0 \n",
    "#         while count < n:\n",
    "#             right = right.next\n",
    "#             count += 1\n",
    "# # 没有第n个节点，直接返回head.next\n",
    "#         if not right:\n",
    "#             return head.next\n",
    "#         while right.next:\n",
    "#             left = left.next\n",
    "#             right = right.next\n",
    "#         left.next = left.next.next\n",
    "\n",
    "#         return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        tmp, pre, cur = head, head, head\n",
    "        for i in range(n): cur = cur.next\n",
    "        if cur == None: \n",
    "            head = head.next \n",
    "            return head\n",
    "        while cur: tmp, pre, cur = pre, pre.next, cur.next\n",
    "        tmp.next = pre.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0, head)\n",
    "        stack = list()\n",
    "        cur = dummy\n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            cur = cur.next\n",
    "        \n",
    "        for i in range(n):\n",
    "            stack.pop()\n",
    "\n",
    "        prev = stack[-1]\n",
    "        prev.next = prev.next.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        left = right = head\n",
    "        count = 0\n",
    "        while count < n and right:\n",
    "            count += 1\n",
    "            right = right.next\n",
    "        if count < n:\n",
    "            return head\n",
    "        if not right:\n",
    "            return head.next\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "\n",
    "        left.next = left.next.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1, head)\n",
    "        fast, slow = dummy, dummy\n",
    "        while n:\n",
    "            fast = fast.next\n",
    "            n -= 1\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0, head)\n",
    "        first = head\n",
    "        second = dummy\n",
    "        # 快指针先走n\n",
    "        for i in range(n):\n",
    "            first = first.next\n",
    "        # 慢指针走到n\n",
    "        while first:\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "        # 对需要处理的倒数第n个节点进行删除\n",
    "        second.next = second.next.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        fast = slow =head\n",
    "        count = 0\n",
    "        while count < n:\n",
    "            fast = fast.next\n",
    "            count += 1\n",
    "        if not fast:\n",
    "            return head.next\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        ans = ListNode(0, head)\n",
    "        slow = ans\n",
    "        fast = head\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        slow.next = slow.next.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        slow = fast = dummy\n",
    "        for i in range(n):\n",
    "            fast = fast.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "\n",
    "        # 用双指针，快慢指针做法\n",
    "            #构建虚拟节点\n",
    "        dummy_node = ListNode(0,head)\n",
    "\n",
    "        #快指针先走n+1步。 先走n+1步，是因为想让slow指针指向倒数第n个节点的前一个节点\n",
    "        n += 1\n",
    "        fast = dummy_node\n",
    "        while n and fast != None: #这里的判断条件一开始想错了，不是fast.next != None 。 因为我们的fast指针可以一直走下去的\n",
    "            # print(\"fast\",fast.val)\n",
    "            fast = fast.next\n",
    "            n -= 1\n",
    "\n",
    "        slow = dummy_node\n",
    "\n",
    "        while fast != None:\n",
    "            fast = fast.next\n",
    "            # print(\"slow\",slow.val)\n",
    "            slow = slow.next\n",
    "\n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummy_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "\n",
    "        dummy_head = ListNode(next=head)\n",
    "\n",
    "        length = 0\n",
    "        fast = dummy_head\n",
    "        slow = dummy_head\n",
    "\n",
    "        for i in range(n+1):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummy_head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(1)\n",
    "        dummy.next = head\n",
    "        prev, slow, fast = dummy, dummy, dummy\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "\n",
    "        while fast:\n",
    "            prev = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        prev.next = slow.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        new_head = ListNode(next=head)\n",
    "        quick = new_head\n",
    "        slow = new_head\n",
    "        i = 0\n",
    "        while quick.next:\n",
    "            quick = quick.next\n",
    "            if i < n:\n",
    "                i += 1\n",
    "            else:\n",
    "                slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        cur = ListNode(next = head)\n",
    "        i = 0\n",
    "        op = cur\n",
    "        p = cur\n",
    "        while cur:\n",
    "            if i > n:\n",
    "                p = p.next\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        p.next = p.next.next\n",
    "        return op.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        node1, node2, pre = head, head, None\n",
    "        for i in range(1, n):node1 = node1.next\n",
    "        while node1.next:\n",
    "            node1 = node1.next\n",
    "            pre = node2\n",
    "            node2 = node2.next\n",
    "        if pre:\n",
    "            pre.next = node2.next\n",
    "        else:\n",
    "            head = node2.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        fast, slow = head, head\n",
    "        for i in range(n):\n",
    "            fast = fast.next\n",
    "        pre = None\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        if pre == None:\n",
    "            return head.next\n",
    "        else:\n",
    "            pre.next = slow.next\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        cur = ListNode(next = head)\n",
    "        i = 0\n",
    "        op = cur\n",
    "        p = cur\n",
    "        while cur:\n",
    "            if i > n:\n",
    "                p = p.next\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        p.next = p.next.next\n",
    "        return op.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        left = right = head\n",
    "        count = 0 \n",
    "        while count < n:\n",
    "            right = right.next\n",
    "            count += 1\n",
    "        if not right:\n",
    "            return head.next\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        left.next = left.next.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        cur = ListNode(next = head)\n",
    "        i = 0\n",
    "        op = cur\n",
    "        p = cur\n",
    "        while cur:\n",
    "            if i > n:\n",
    "                p = p.next\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        p.next = p.next.next\n",
    "        return op.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy=ListNode(next=head)\n",
    "        left=right=dummy\n",
    "        for _ in range(n):\n",
    "            right=right.next\n",
    "        while right.next:\n",
    "            left=left.next   \n",
    "            right=right.next\n",
    "        left.next=left.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy_node = ListNode(0)\n",
    "        dummy_node.next = head\n",
    "\n",
    "        p_slow, p_fast = dummy_node, dummy_node\n",
    "        for i in range(n):\n",
    "            p_fast = p_fast.next\n",
    "        \n",
    "        while p_fast and p_fast.next:\n",
    "            p_slow = p_slow.next\n",
    "            p_fast = p_fast.next\n",
    "        \n",
    "        if p_slow:\n",
    "            p_slow.next = p_slow.next.next\n",
    "        \n",
    "        return dummy_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        step, blank_node = 1, ListNode(-1, head)\n",
    "        cur, left, right = blank_node, head, head\n",
    "        \n",
    "        while right:\n",
    "            if step <= n:\n",
    "                right = right.next\n",
    "                step += 1\n",
    "            else:\n",
    "                right = right.next\n",
    "                left = left.next\n",
    "                cur = cur.next\n",
    "\n",
    "        cur.next = left.next\n",
    "        return blank_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        fast = slow =head\n",
    "        count = 0\n",
    "        while count < n:\n",
    "            fast = fast.next\n",
    "            count += 1\n",
    "        if not fast:\n",
    "            return head.next\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        tmp = []\n",
    "        cur = head\n",
    "        dump = ListNode(next=head)\n",
    "        tmp.append(dump)\n",
    "        while cur:\n",
    "            tmp.append(cur)\n",
    "            cur = cur.next\n",
    "        tmp[len(tmp) - n - 1].next = tmp[len(tmp) - n].next\n",
    "        return dump.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(next=head)\n",
    "        fast = head\n",
    "        slow = dummy\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head==None:\n",
    "            return None\n",
    "        \n",
    "        virHead = ListNode(None)\n",
    "        virHead.next = head\n",
    "        \n",
    "        slow = fast = virHead\n",
    "\n",
    "        for _ in range(n+1):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while(fast):\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "        return virHead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        node = self.getNthFromEnd(dummy,n+1)\n",
    "        node.next = node.next.next\n",
    "        return dummy.next\n",
    "\n",
    "    def getNthFromEnd(self,head,n):\n",
    "        fast = head\n",
    "        for i in range(n):\n",
    "            fast = fast.next\n",
    "        slow = head\n",
    "        while fast!=None:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def getLength(head: ListNode) -> int:\n",
    "            length = 0\n",
    "            while head:\n",
    "                length += 1\n",
    "                head = head.next\n",
    "            return length\n",
    "        \n",
    "        dummy = ListNode(0, head)\n",
    "        length = getLength(head)\n",
    "        cur = dummy\n",
    "        for i in range(1, length - n + 1):\n",
    "            cur = cur.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        fast = head\n",
    "        # get node_len\n",
    "        node_len = 1\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            node_len += 1\n",
    "\n",
    "        if node_len==n:\n",
    "            return head.next\n",
    "\n",
    "        fast = head\n",
    "        for _ in range(node_len-n-1):\n",
    "            fast = fast.next\n",
    "\n",
    "        if fast.next:\n",
    "            fast.next = fast.next.next\n",
    "        else:\n",
    "            head = head.next\n",
    "\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        # def get_length(head):\n",
    "        #     length = 0\n",
    "        #     while head:\n",
    "        #         length += 1\n",
    "        #         head = head.next\n",
    "        #     return length\n",
    "        \n",
    "        # dummy = ListNode(0, head)\n",
    "        # length = get_length(head)\n",
    "        # cur = dummy\n",
    "        # for i in range(1, length-n+1):\n",
    "        #     cur = cur.next\n",
    "        # cur.next = cur.next.next\n",
    "        # return dummy.next\n",
    "\n",
    "        # 双指针\n",
    "        dummy = ListNode(0, head)\n",
    "        slow, fast = dummy, head\n",
    "        for i in range(n):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def lenghth(head):\n",
    "            lgh = 0\n",
    "            while head:\n",
    "                lgh += 1\n",
    "                head = head.next\n",
    "            return lgh\n",
    "        dummynode = ListNode(0, head)\n",
    "        cur = dummynode\n",
    "        for i in range(lenghth(head) - n):\n",
    "            cur = cur.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummynode.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def findFromEnd(self, head: ListNode, k: int) -> ListNode:\n",
    "        p1 = head\n",
    "        # p1 先走 k 步\n",
    "        for i in range(k):\n",
    "            p1 = p1.next\n",
    "        p2 = head\n",
    "        # p1 和 p2 同时走 n - k 步\n",
    "        while p1 != None:\n",
    "            p2 = p2.next\n",
    "            p1 = p1.next\n",
    "        # p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点\n",
    "        return p2\n",
    "\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        # 虚拟头结点\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        # 删除倒数第 n 个，要先找倒数第 n + 1 个节点\n",
    "        x = self.findFromEnd(dummy, n + 1)\n",
    "        # 删掉倒数第 n 个节点\n",
    "        x.next = x.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        length = 0\n",
    "        pointer = head\n",
    "        while pointer:\n",
    "            length += 1\n",
    "            pointer = pointer.next\n",
    "        if length - n == 0:\n",
    "            return head.next\n",
    "        pointer = head\n",
    "        for i in range(length - n - 1):\n",
    "            pointer = pointer.next\n",
    "        pointer.next = pointer.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        \n",
    "        length = 0\n",
    "        dummy = ListNode(0) \n",
    "        dummy.next = arr = head           \n",
    "        curr = dummy\n",
    "\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next       \n",
    "\n",
    "        for i in range(1, length - n + 1):\n",
    "            curr = curr.next\n",
    "        \n",
    "        curr.next = curr.next.next\n",
    "\n",
    "        return dummy.next\n",
    "        \n",
    "        '''\n",
    "\n",
    "        lenth = 0\n",
    "        dummy = ListNode(-1)\n",
    "        curr = dummy\n",
    "        dummy.next = head\n",
    "\n",
    "        while head:\n",
    "            lenth += 1\n",
    "            head = head.next\n",
    "        \n",
    "        for i in range(1, lenth-n+1):\n",
    "            curr = curr.next\n",
    "        curr = curr.next.next\n",
    "\n",
    "        return dummy.next\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        node=ListNode(next=head)\n",
    "        s1=s2=node\n",
    "        while n:\n",
    "            s2=s2.next\n",
    "            n-=1\n",
    "        while s2.next:\n",
    "            s1=s1.next\n",
    "            s2=s2.next\n",
    "            n-=1\n",
    "        s1.next=s1.next.next\n",
    "        return node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        count = 0\n",
    "        x = head\n",
    "        #先统计一共有几个节点\n",
    "        while x:\n",
    "            count += 1\n",
    "            x = x.next\n",
    "        index = 0\n",
    "        #涉及两个指针将删除之后的两部分接起来\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        #考虑两种特殊情况\n",
    "        if count == 1 and n == 1:\n",
    "            return None\n",
    "        if n == count:\n",
    "            return head.next\n",
    "        #查找目标位置\n",
    "        while index < count - n - 1:\n",
    "            slow = slow.next \n",
    "            fast = fast.next\n",
    "            index += 1\n",
    "        slow.next = fast.next\n",
    "        return head\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0,head)\n",
    "        node=dummy\n",
    "        i = 0\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        a = length - n \n",
    "        while i < a:\n",
    "            node = node.next\n",
    "            i += 1\n",
    "        node.next = node.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, k: int) -> ListNode:\n",
    "        cur = ListNode(0, head)\n",
    "        p = head\n",
    "        q = cur\n",
    "        while k - 1:\n",
    "            p = p.next\n",
    "            k -= 1\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        q.next = q.next.next\n",
    "        return cur.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        tmp, cur = ListNode(0, head), head\n",
    "        pre = tmp\n",
    "        for i in range(n): cur = cur.next\n",
    "        while cur: pre, cur = pre.next, cur.next\n",
    "        pre.next = pre.next.next\n",
    "        return tmp.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        def get_length(head):\n",
    "            length = 0\n",
    "            while head:\n",
    "                length += 1\n",
    "                head = head.next\n",
    "            return length\n",
    "        \n",
    "        dummy = ListNode(0, head)\n",
    "        length = get_length(head)\n",
    "        cur = dummy\n",
    "        for i in range(1, length-n+1):\n",
    "            cur = cur.next\n",
    "        cur.next = cur.next.next\n",
    "        return dummy.next\n",
    "\n",
    "        # 双指针"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "\n",
    "        dummyhead = ListNode(0)\n",
    "        dummyhead.next = head\n",
    "        left = dummyhead\n",
    "        right = dummyhead\n",
    "        while n:\n",
    "            right = right.next\n",
    "            n -= 1\n",
    "\n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        \n",
    "        tmp = left.next\n",
    "        left.next = left.next.next\n",
    "        del tmp\n",
    "        return dummyhead.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
